package DataStructures.BinaryTree;

/**
 * @author ：ALi
 * @date ：Created in 2021/11/29 19:42
 * @description：线索化二叉树
 * @modified By：
 * @version: $
 */
public class BinaryTree {
    public static void main(String[] args) {

        Hero2 root2 = new Hero2(1, "宋江");
        Hero2 hero12 = new Hero2(3, "吴用");
        Hero2 hero22 = new Hero2(6, "卢俊义");
        Hero2 hero32 = new Hero2(8, "林冲");
        Hero2 hero42 = new Hero2(14, "卢俊义");
        Hero2 hero52 = new Hero2(10, "林冲");
        root2.setLeft(hero12);
        root2.setRight(hero22);
        hero12.setLeft(hero32);
        hero12.setRight(hero52);
        hero22.setLeft(hero42);

        HeroList2 binaryTree2 = new HeroList2();
        binaryTree2.setHead(root2);
        binaryTree2.midClue(root2);
        System.out.println(hero52.getLeft());
        System.out.println(hero52.getRight());
        System.out.println("中序打印节点");
        binaryTree2.midOrder();
    }

}

class Hero2 {
    private int id;
    private String name;
    private Hero2 left;
    private Hero2 right;
    private int LeftType;//0是左孩子，1是前驱节点
    private int RightType;//0是右孩子，1是后继节点

    public int getId() {
        return id;
    }

    public String getName() {
        return name;
    }

    public Hero2() {
    }

    public Hero2(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Hero2{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    public void setLeft(Hero2 left) {
        this.left = left;
    }

    public void setRight(Hero2 right) {
        this.right = right;
    }

    public Hero2 getLeft() {
        return left;
    }

    public Hero2 getRight() {
        return right;
    }

    public void setId(int id) {
        this.id = id;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getLeftType() {
        return LeftType;
    }

    public void setLeftType(int leftType) {
        LeftType = leftType;
    }

    public int getRightType() {
        return RightType;
    }

    public void setRightType(int rightType) {
        RightType = rightType;
    }
}
class HeroList2 {
    private Hero2 head;
    private Hero2 proNote = null;

    public HeroList2() {
    }

    @Override
    public String toString() {
        return "HeroList2{" +
                "head=" + head +
                ", proNote=" + proNote +
                '}';
    }

    public void setHead(Hero2 head) {
        this.head = head;
    }

    public Hero2 getHead() {
        return head;
    }

    public Hero2 getProNote() {
        return proNote;
    }

    public void setProNote(Hero2 proNote) {
        this.proNote = proNote;
    }

    public void midClue(Hero2 root){

        if (root == null){
            System.out.println("二叉树为空");
            return;
        }
        //先遍历左孩子
        if (root.getLeft() != null){
            midClue(root.getLeft());
        }
        //再遍历自身
            //设置前驱节点
        if (root.getLeft() == null){
            root.setLeft(proNote);
            root.setLeftType(1);
        }
            //设置后继节点
        if (proNote != null && proNote.getRight() == null){
            this.proNote.setRight(root);
            proNote.setRightType(1);
        }
        proNote = root;

        //最后遍历右孩子
        if (root.getRight() != null){
            midClue(root.getRight());
        }
    }

    //中序遍历线索二叉树
    public void midOrder() {
        Hero2 node = head;

        while (node != null) {

            //找到中序线索二叉树的第一个节点，并打印
            while (node.getLeftType() == 0) {
                node = node.getLeft();
            }
            System.out.println(node);

            //从第一个节点开始，一次打印其后继节点。
            // 若没有后继节点就将其右孩子作为当前节点，继续遍历，直到退出循环
            while (node.getRightType() == 1) {
                node = node.getRight();
                System.out.println(node);
            }
            node = node.getRight();

        }
    }
}